package com.kyle.java.sorting;

import java.util.Arrays;

/**
 * @author kyle
 * @version 1.0
 * @date 2021/4/10 8:32
 *
 *
 * 插入排序算法思路：
 *  1. 将数组分为 已排序、未排序  的两个队列
 *  2. 每次循环从未排序的序列对头取数 按顺序插入到已排序的序列中
 *  3. 结束条件：未排序的序列队列为空
 *
 *  举例  {3,5,1,2,0}
 *            未排序        已排序
 *       1.   {3,5        1,2,0}
 *       2.   {1,3,5        2,0}
 *       3.   {1,2,3,5,       0}*
 *       4    {0,1,3,5,7,9}
 *
 */
public class InsertSorting {
    public static void main(String[] args) {
        int[] array =  new int[10000];
        for(int i = 0 ;i<array.length;i++) {
            array[i] = (int) (Math.random() * 20000) + 1;  //产生从1 - 10000的随机数
        }
        intArrayInsertSortingASC(array);
        System.out.println(Arrays.toString(array));
    }

    public static void intArrayInsertSortingASC(int[] array){
            // 数组为 {3,5,1,2,0}
          for(int i = 1 ; i < array.length ; i++){  // 假如数组长度是5， 则未排序队列数量为4，循环4次 故 i-1
              //每次循环 将array[i]  插入到  array[0]~array[i-1] 里
              int insertIndex = 0;
              for(int j = 0 ; j < i ; j++){   //遍历查找有序列表，确定插入位置

                   if(array[i] > array[j])  //要插入的数值大于 当前遍历的数值
                   {
                       insertIndex = j+1; // 插入位置更新
                   }

               }
              //根据插入位置，插入数值，并将后续 有序列表 元素移动位置
                  //tips：抽象成 在 [0-i]的下标范围内 根据insertIndex 插入a[i]
              int temp = array[i];
              for(int j = i; j>insertIndex ; j--){ //将插入位置后面的元素进行移位
                    array[j] = array[j-1];
              }
              array[insertIndex]  = temp;  //将元素插入到位置
          }
    }
    }
